# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/21 15:50
功能描述: 
"""

"""
什么是平摊分析？
    平摊分析是一种用于分析一系列操作平均成本的算法。它的核心思想是：即使序列中的单个操作可能非常昂贵（耗时很长），但通过将其成本 “分摊” 到整个序列的其他操作上，我们可以证明整个序列的平均成本是很低的。
    这与最坏情况分析（Worst-Case Analysis）不同。最坏情况分析关注的是序列中某一个操作的最大可能成本，而平摊分析关注的是整个序列的总操作成本除以操作次数，得到的平均成本。
    
为什么需要平摊分析？
    在很多数据结构中，大多数操作都很快，但偶尔会出现一个非常慢的操作。
    例如：
    动态数组（ArrayList）的 append 操作：大多数情况下，append 只是在数组末尾添加一个元素，时间复杂度是 O (1)。但当数组满了之后，它需要创建一个新的、更大的数组，并将所有元素复制过去，这个操作的时间复杂度是 O (n)。
    栈（Stack）的 pop 和 push 操作：通常是 O (1)。但如果我们有一个 multi-pop（弹出 k 个元素）操作，它的时间复杂度是 O (k)。
    二进制计数器的 increment 操作：每次加一，可能需要翻转多个位（例如，从 111 到 1000 需要翻转 4 位）。
    如果我们只用最坏情况分析，会得出这些操作的时间复杂度是 O (n) 或 O (k)，这显然过于悲观，不能准确反映它们在实际应用中的良好性能。平摊分析就是为了更准确地刻画这种 “大部分快，偶尔慢” 的场景。


平摊分析的三种主要方法
2.1 聚合分析 (Aggregate Analysis)
    思路：直接计算一个序列中所有操作的总 cost，然后除以操作的数量，得到每个操作的平均（平摊）cost。
    
    步骤：
        设 n 为操作序列的长度。
        找到总 cost T(n) 的一个上界。
        平摊 cost a(n) = T(n) / n。
        
    例子：二进制计数器的 increment 操作
    一个 k 位的二进制计数器，初始为 0。increment 操作会将计数器加一。每次加一，从右往左翻转位，直到遇到第一个 0 并将其翻转为 1，它右边的所有 1 都翻转为 0。
        最坏情况 
            cost：每次 increment 都需要翻转所有 k 位，cost 为 O (k)。
        聚合分析：
            考虑从 0 到 n-1 的 n 次 increment 操作。
            第 0 位（最低位）每 1 次操作翻转 1 次。
            第 1 位每 2 次操作翻转 1 次。
            第 2 位每 4 次操作翻转 1 次。
            ...
            第 i 位每 2^i 次操作翻转 1 次。
            ...
            第 k-1 位每 2^(k-1) 次操作翻转 1 次。
            总翻转次数 T(n) <= n + n/2 + n/4 + ... + 1 (当 n <= 2^k 时)
            这是一个等比数列求和，T(n) < 2n。
            因此，平摊 cost a(n) = T(n) / n < 2n / n = 2。
            所以，increment 操作的平摊 cost 是 O (1)。

2.2 会计方法 (Accounting Method)
    思路：
    这是一种更直观、更像 “记账” 的方法。我们为每种操作赋予一个平摊 cost（记为 amortized_cost）。这个平摊 cost 可能高于或低于其实际的真实 cost（记为 actual_cost）。
        当 amortized_cost > actual_cost 时，我们将差额（credit）“存入” 数据结构中的某些特定位置（可以想象成给某些元素打上 “欠条”）。
        当 amortized_cost < actual_cost 时，我们就用之前存下的 credit 来支付差额。
    关键 invariant（不变式）：在任何操作序列中，总 credit 永远不能为负。这保证了我们存入的 “存款” 足够支付未来昂贵操作的 “透支”。
    例子：动态数组的 append 操作
    假设数组初始容量为 1。当数组满时，append 操作会触发扩容，通常是创建一个容量翻倍的新数组，并复制所有元素。
        append 到未满数组的 actual cost: c (c是一个常数，例如 1)。
        append 到已满数组（需要扩容）的 actual cost: n + c (复制 n 个元素，再加上新元素)。
    我们希望证明 append 的平摊 cost 是 O (1)。我们设定平摊 cost a = 3c。
    场景 1: 数组未满，执行 append
        actual_cost = c
        amortized_cost = 3c
        credit 增加 3c - c = 2c。我们可以将这 2c 的 credit 记在新添加的元素上。
    场景 2: 数组已满（容量为 n），执行 append
        actual_cost = n * c (复制) + c (添加新元素) = c(n + 1)
        amortized_cost = 3c
        此时，数组中有 n 个元素，每个元素都带有 2c 的 credit，总 credit 为 n * 2c。(注意：这个n*2c是你账户上存的，即你之前攒下来的！)
        我们需要支付的差额是 actual_cost - amortized_cost = c(n + 1) - 3c = c(n - 2)。(注意：这个c(n-2)是你欠的!)
        我们检查总 credit 是否足够支付这个差额：n * 2c >= c(n - 2) 吗？
        2n >= n - 2，即 n + 2 >= 0，这总是成立的（因为 n 是正整数）。
        支付后，总 credit 变为 2nc - c(n - 2) = c(2n - n + 2) = c(n + 2)。(这是你账户上应该存下来的)
        这次 append 操作添加了一个新元素，根据我们的规则，我们需要为它预留 2c 的 credit。所以，最终的总 credit 应该是 c(n + 2) - 2c = cn。
        扩容后，数组容量变为 2n，新数组中有 n + 1 个元素。其中 n 个是旧元素（它们的 credit 由于刚才的扩容动作已经被使用了一部分），1 个是新元素。
        我们可以认为，这 cn 的总 credit 均匀分布在新数组的 2n 个 “槽位” 上，或者简单地记在系统中，用于支付下一次扩容。关键是，总 credit 非负。

    通过这种方式，我们证明了每次 append 操作的平摊 cost 是 O(1)。
    
    Q:这次 append 操作添加了一个新元素，根据我们的规则，我们需要为它预留 2c 的 credit。所以，最终的总 credit 应该是 c(n + 2) - 2c = cn。为什么不是+2c而是-2c?
    A:在会计方法中，每个新添加的元素需要预留 2c 的 credit（这是我们设定的规则，用于未来支付扩容成本）。
    当执行一次需要扩容的 append 操作后：
        我们先计算支付差额后的总 credit 为 c(n + 2)。
        但这次 append 新增了一个元素，按照规则，必须为这个新元素预留 2c 的 credit。
        因此，需要从当前总 credit 中扣除这 2c，最终总 credit 为 c(n + 2) - 2c = cn。
    简单来说，“-2c” 是因为新增的元素需要占用 2c 的 credit 储备，所以要从总 credit 中减去这部分预留金。



"""
